package GraphType.shortestPath;

import java.util.Scanner;

/**
 * 问题描述:迷宫由n行m列的单元格组成( n , m都小于等于50 )每个单元格要么是空地，要么是障碍物。
 * 现请你找到一条从起点到终点的最短路径长度。
 * 解决方案：DFS
 * 定义4个带优先级的前进方向，从起点开始进行试探，
 * 当走到空地，则将空地标记为已访问，
 * 当遇到障碍物，则改变方向继续进行试探，
 * 当达到终点就记录这条路径的长度，然后进行回溯来尝试另一种路径解，
 * 每次回溯到上一个点都将之设置为未访问。通过不断尝试，最终找到最优路径。
 * 例子：
 * 输入：
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3
 * 输出：7
 */
public class DFS {
    static int p, q, startX, startY, min = 99999;
    static int[][] a = new int[10][10];//1表示空地，2表示障碍物
    static int v[][] = new int[10][10];//0表示未访问，1表示已访问
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] arr = scanner.nextLine().split(" ");
        int m = Integer.parseInt(arr[0]);
        int n = Integer.parseInt(arr[1]);
        for (int i = 1; i <= m; i++) {
            String[] split = scanner.nextLine().split(" ");
            for (int j = 1; j <= n; j++) {
                a[i][j] = Integer.parseInt(split[j - 1]);
            }
        }
        //起点坐标，终点坐标
        String[] loc = scanner.nextLine().split(" ");
        startX = Integer.parseInt(loc[0]);
        startY = Integer.parseInt(loc[1]);
        p = Integer.parseInt(loc[2]);
        q = Integer.parseInt(loc[3]);
        printMatrix(a);
        System.out.printf("起点：(%d,%d)", startX, startY);
        System.out.printf("终点：(%d,%d)", p, q);
        v[startX][startY] = 1;
        dfs(startX, startY, 0);
        System.out.printf("最短路径长度为：%d", min);
    }

    static void dfs(int x, int y, int step) {
        if (x == p && y == q) { //到达终点的情况
            if (step < min) {
                min = step;
            }
            return; //回退
        }
        //顺时针进行试探
        for (int i = 0; i < 4; i++) {
            if (a[x+dx[i]][y+dy[i]]==1 && v[x+dx[i]][y+dy[i]]==0){
                v[x+dx[i]][y+dy[i]] = 1;
                dfs(x+dx[i], y+dy[i], step + 1);
                v[x+dx[i]][y+dy[i]] = 0; //回溯
            }
        }


        return; //无路可走也只有回退
    }

    static void dfs1(int x, int y, int step) {
        if (x == p && y == q) { //到达终点的情况
            if (step < min) {
                min = step;
            }
            return; //回退
        }
        //顺时针进行试探
        //右
        if (a[x][y + 1] == 1 && v[x][y + 1] == 0) {
            v[x][y + 1] = 1;
            dfs(x, y + 1, step + 1);
            v[x][y + 1] = 0; //回溯
        }
        //下
        if (a[x + 1][y] == 1 && v[x + 1][y] == 0) {
            v[x + 1][y] = 1;
            dfs(x + 1, y, step + 1);
            v[x + 1][y] = 0; //回溯
        }
        //左
        if (a[x][y - 1] == 1 && v[x][y - 1] == 0) {
            v[x][y - 1] = 1;
            dfs(x, y - 1, step + 1);
            v[x][y - 1] = 0; //回溯
        }
        //上
        if (a[x - 1][y] == 1 && v[x - 1][y] == 0) {
            v[x - 1][y] = 1;
            dfs(x - 1, y, step + 1);
            v[x - 1][y] = 0; //回溯
        }
        return; //无路可走也只有回退
    }

    public static void printMatrix(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.printf("%d\t", a[i][j]);
            }
            System.out.println();
        }
    }
}
